package LearnAlgorithm.a_eclipseHello;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class test0 {
	public static void main(String[] args) {
		test0 test = new test0();
		test.useDeal();
	}
	
	public void useDeal() {
		Scanner scanner = new Scanner(System.in);
		int length = scanner.nextInt();
		int[] arr = new int[length];
		for (int i = 0; i < length; i++) {
			arr[i] = scanner.nextInt();
		}
		int diff = scanner.nextInt();
		deal(arr, diff);
	}
	
	public void useDeal(int[] arr, int diff) {
		deal(arr, diff);
	}
	
	public void deal(int[] nums, int diff) {
		for (int i = 0; i < nums.length - 2; i++) {
			for (int j = i + 1; j < nums.length - 1; j++) {
				if (nums[j] - nums[i] != diff) {
					continue;
				}
				for (int k = j + 1; k < nums.length; k++) {
					if (nums[k] - nums[j] != diff) {
						continue;
					}
					System.out.println("(" + nums[i] + ", " + nums[j] + ", " + nums[k] + ") 是算术三元组：" + 
							nums[k] + " - " + nums[j] + " == " + diff + 
							" 且 " + nums[j] + " - " + nums[i] + " == " + diff + " 。");
				}
			}
		}
	}
	
	/**
	 * O(N^2)
	 * @param nums
	 * @param diff
	 * @return
	 */
	public int deal2(int[] nums, int diff) {
		int count = 0;
		l1: for (int i = 0; i < nums.length - 2; i++) {
			boolean flag = false;
			l2: for (int j = i + 1; j < nums.length - 1; j++) {
				if (nums[i] + diff != nums[j]) {
					continue l2;
				} else {
					flag = true;
					break;
				}
			}
			if (flag) {
				l3: for (int k = i + 2; k < nums.length; k++) {
					if (nums[i] + diff * 2 != nums[k]) {
						continue l3;
					} else {
						count++;
						continue l1;
					}
				}
			} else {
				continue l1;
			}
		}
		return count;
	}
	
	/**
	 * O(N^2)
	 * @param nums
	 * @param diff
	 * @return
	 */
	public int deal3(int[] nums, int diff) {
		int count = 0;
		Set<Integer> helper = new HashSet<Integer>();
		for (int i : nums) {
			helper.add(i);
		}
		for (int i : nums) {
			if (helper.contains(i + diff) && helper.contains(i + diff * 2)) {
				count++;
			}
		}
		return count;
	}
	
	/**
	 * O(N)
	 * 利用了KMP思想
	 * 不回头
	 * @param nums
	 * @param diff
	 * @return
	 */
	public int deals(int[] nums, int diff) {
        int ans = 0;
        int n = nums.length;
        for (int i = 0, j = 1, k = 2; i < n - 2 && j < n - 1 && k < n; i++) {
            j = Math.max(j, i + 1);//这里利用了不回头的思想
            while (j < n - 1 && nums[j] - nums[i] < diff) {
                j++;
            }
            if (j >= n - 1 || nums[j] - nums[i] > diff) {
                continue;
            }
            k = Math.max(k, j + 1);
            while (k < n && nums[k] - nums[j] < diff) {
                k++;
            }
            if (k < n && nums[k] - nums[j] == diff) {
                ans++;
            }
        }
        return ans;
    }

}
